package com.wh.usercenter3.util;

import com.wh.usercenter3.pojo.Score;
import com.wh.usercenter3.pojo.User;

import java.util.*;

public class AlgorithmUtil {

    /**
     * 编辑距离算法 => 用户根据标签相似度推荐
     * @param word1
     * @param word2
     * @return
     */
    public static int minDistance(String word1, String word2){
        int n = word1.length();
        int m = word2.length();

        if(n * m == 0)
            return n + m;

        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++){
            d[i][0] = i;
        }

        for (int j = 0; j < m + 1; j++){
            d[0][j] = j;
        }

        for (int i = 1; i < n + 1; i++){
            for (int j = 1; j < m + 1; j++){
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1))
                    left_down += 1;
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return d[n][m];
    }

    /**
     *  编辑距离算法改造
     * @param str1
     * @param str2
     * @return 返回一个分数
     */
    public static int minDistances(List<String> str1, List<String> str2){
        int n = str1.size();
        int m = str2.size();

        if(n * m == 0)
            return n + m;

        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++){
            d[i][0] = i;
        }

        for (int j = 0; j < m + 1; j++){
            d[0][j] = j;
        }

        for (int i = 1; i < n + 1; i++){
            for (int j = 1; j < m + 1; j++){
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (!Objects.equals(str1.get(i - 1), str2.get(j - 1)))
                    left_down += 1;
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return d[n][m];
    }

    /**
     * 根据分数情况维护动态数组
     * @param topList
     * @param loginUser
     * @param user
     * @return
     */
    public static LinkedList<Score> sortTopList(LinkedList<Score> topList, String[] loginUser, Map.Entry<User, String[]> user) {
        int score = minDistances(Arrays.asList(loginUser), Arrays.asList(user.getValue()));
        Score newScore = new Score();
        for (int i = 0; i < topList.size(); i++) {
            Integer scoreI = topList.get(i).getScore();
            if (score < scoreI) {
                newScore.setUser(user.getKey());
                newScore.setScore(score);
                topList.add(i, newScore);
                return topList;
            }
        }
        newScore.setUser(user.getKey());
        newScore.setScore(score);
        topList.add(newScore);
        return topList;
    }
}
